Video encoding and decoding is known in the art. Some video coding and decoding formats employ a technique known as intra-prediction which often relies upon a so-called minimum description length (MDL) principle. The intra-prediction technique often employs two stages: selecting a prediction mode (from amongst a plurality of candidate prediction modes) and then applying the selected prediction mode. The intra-prediction technique serves to minimize a total description length that includes a description length of the selected prediction mode and a description length of residuals resulting from using the selected prediction mode. The Advanced Video Coding (AVC) video compression standard (a block-oriented motion-compensation-based codec standard developed by the ITU-T Video Coding Experts Group (VCEG) together with the ISO/IEC Moving Picture Experts Group (MPEG)) and the High Efficiency Video Coding (HEVC) video compression standard (that was jointly developed by the ISO/IEC Moving Picture Experts Group and ITU-T Video Coding Experts Group as ISO/IEC 23008-2 MPEG-H Part 2 and ITU-T H.265) are examples of video coding standards that utilize intra-prediction.
The MDL principle minimization step provides a sound mechanism against over-fitting. A brute-force implementation of the minimization step, however, necessitates examining all possible prediction modes and determining the associated coding cost for each of these modes. When the number of available modes is large (35 in HEVC, for example), the computational complexity involved can be excessive. Furthermore, in order to further improve rate distortion performance, a straightforward method is to define even more intra-prediction modes while leveraging MDL to take advantage of these additional modes. Such benefits are currently only attained, however, by also increasing even further the computational overhead that accompanies the additional modes.